The discrete Fourier transform (DFT) is a well known algorithm used in digital signal processing for transforming data-sets between time and frequency domains. This transform is frequently used in several fields of digital signal processing such as signal and image processing, digital filtering, frequency analysis, speech recognition, etc. The fast Fourier transform (FFT) is an efficient algorithm for computing the Discrete Fourier Transform. The FFT takes advantage of the divide and conquer approach, in which an N-point DFT is broken down into N number of X point DFTs, where X is the radix number. This results in considerable savings of computation time. If the sample size is a power of two, the transform can be recursively sub-divided into equal sized sub-transforms, processed, and reconstructed with a series of butterfly circuits. A radix-2 butterfly circuit computes two outputs that are a weighted sum of two sub-transform inputs to the circuit. Sub-transforms are combined in a reverse recursive fashion to compute the FFT of the entire sample size.
If the time series contains N=2M samples, then for the N frequency domain samples the FFT entails Nlog2 N multiply operations (assuming a radix-2 butterfly). In contrast, the DFT algorithm requires N2 multiply operations. The FFT advantage grows as N increases. Thus, an 8 point DFT and FFT require 64 and 24 multiply operations, respectively, while an 8192 point DFT and FFT require 67.1×106 and 106,496 multiply operations, respectively.
A number of wireless standards utilize inverse FFT and FFT operations for respective modulation and demodulation of signals. In the 3GPP LTE wireless standard, the majority of supported bandwidths can be represented with datasets having a sample size that is a power-of-two (e.g. 2048-points for the 20 MHz bandwidth). Datasets of these bandwidths can be modulated and demodulated using the fast Fourier transform.
However, in many applications a sample size that is not a power of two is required. For example, the 3GPP LTE wireless standard requires support for several bandwidths that are not a power of two. In particular, in order to modulate and demodulate the 15 MHz bandwidth defined in the standard's specification, an FFT over 1536 points is required. For support of the Multi-Media Broadcast over a Single Frequency Network (MBSFN) option in the standard, a 3072-point FFT is required. These sample sizes can each be sub-divided and processed as three sub-transforms that are a power of two using FFT processing. However, in order to combine the three processed sub-transforms, a radix-3 processing stage is needed to compute a weighted sum of three sub-transforms to produce the DFT of the entire sample size.
In prior art implementations, the radix-3 combinational stage has been implemented as a full-parallel circuit requiring at least three complex multipliers and six complex add/subtracts. This is in addition to a FFT module for processing the sub-transforms that are a power-of-two sample size. The radix-3 stage is expensive in resource terms, but permits a streaming throughput, allowing processing of a complex data sample per clock cycle. However, in general, wireless communication systems do not require the very high throughput of a streaming FFT, and are resource sensitive. For this reason, a full-parallel implementation of the radix-3 stage is undesirable. The radix-3 processing may also be implemented within the FFT module itself. However, this has the disadvantage of requiring modifications to the FFT circuitry, adding significant complexity to the control logic and datapath.
The present invention may address one or more of the above issues.